/**
 * 作用：利用广度优先搜索算法+队列的数据结构，解决迷宫问题。
 * 
 * 日期：2019-10-29
 * 
 * 参考：http://akaedu.github.io/book/ch12s04.html
 */
#include <stdio.h>
#include <stdlib.h>

struct point
{
    int row;
    int col
};

struct point queue[512];

int rowmax = 5, colmax = 5;
int mem[5][5] = {
    {0, 1, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0},
};

/* 记录前一个点的位置 */
struct point pre[5][5] = {
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}}

};

/* 列首和列尾 */
int head = 0, tail = 0;

/* 入列 */
void enqueue(struct point p)
{
    queue[tail++] = p;
    return;
}

/* 出列 */
struct point dequeue()
{
    return queue[head++];
}

/* 判断是否为空 */
int is_empty()
{
    return head == tail;
}

/* 函数：打印当前迷宫状态 */
void print_mem()
{
    int i = 0, j = 0;
    static int count_num = 0;

    count_num++;

    printf("---------- %d -----------\n", count_num);

    for (i = 0; i < rowmax; i++)
    {
        for (j = 0; j < colmax; j++)
        {
            printf("%4d", mem[i][j]);
        }
        printf("\n");
    }

    return;
}

void visit(int r, int c, struct point p, struct point pnext)
{
    mem[r][c] = 2;

    pnext.row = r;
    pnext.col = c;

    enqueue(pnext);

    pre[r][c] = p;
}

/* 主函数 */
int main()
{
    struct point p = {0, 0};
    struct point pnext;
    int r = 0, c = 0;

    int has_path = 1;

    r = p.row, c = p.col;

    /* 设定当前元素为走过的值并进入队列 */
    mem[r][c] = 2;
    enqueue(p);

    while (r < rowmax - 1 || c < colmax - 1)
    {
        /* 指向队列开头 */
        p = dequeue();
        r = p.row;
        c = p.col;

        /* 搜索 */
        pnext = p;
        if (c + 1 < colmax && mem[r][c + 1] == 0) /* right */
            visit(r, c + 1, p, pnext);
        pnext = p;
        if (r + 1 < rowmax && mem[r + 1][c] == 0) /* down */
            visit(r + 1, c, p, pnext);
        pnext = p;
        if (c - 1 >= 0 && mem[r][c - 1] == 0) /* left */
            visit(r, c - 1, p, pnext);
        pnext = p;
        if (r - 1 >= 0 && mem[r - 1][c] == 0) /* up */
            visit(r - 1, c, p, pnext);

        /* 打印mem数组 */
        print_mem();

        /* 若队首和队尾对齐（队列为空），并且没有达到终点，则没有路径 */
        if (is_empty()) //函数做参数，不要忘了最后的小括号
        {
            has_path = 0;
            break;
        }
    }

    // ender.
    if (has_path)
    {
        printf("Succeed!\n");

        /* 回溯 */
        pnext.row = rowmax - 1;
        pnext.col = colmax - 1;

        r = pnext.row;
        c = pnext.col;
        printf("(%2d,%2d)\n", r, c);
        mem[r][c] = 3;

        while (r != 0 || c != 0)
        {
            pnext = pre[r][c];
            r = pnext.row;
            c = pnext.col;
            printf("(%2d,%2d)\n", r, c);
            mem[r][c] = 3;
        }

        printf("The path is (mark as 3):\n");
        print_mem();
    }
    else
    {
        printf("No path!\n");
    }

    return 0;
}